package org.example;


import java.util.*;
import java.util.Arrays;

public class DFS {
    // 回溯算法解题套路框架
    /*
    result = []
    def backtrack(路径，选择列表):
        if 满足条件
            result.add(路径)
            return

        for 选择 in 选择列表:
            # 做选择
            将该选择从选择列表移除
            路径.add(选择)
            backtrack(路径, 选择列表)
            # 撤销选择
            路径.remove(选择)
            将该选择再加入选择列表
      */
    // 其核心就是for循环里面的递归，在递归调用之前[做选择]，在递归调用之后[撤销选择]

    // 全排列
    // 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
    // 示例 1：
    // 输入：nums = [1,2,3]
    // 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    static class Permute {
        List<List<Integer>> res = new LinkedList<>();

        public List<List<Integer>> permute(int[] nums) {
            // 记录路径
            LinkedList<Integer> track = new LinkedList<>();
            // 路径中的元素会被标记为true，避免重复使用
            boolean[] used = new boolean[nums.length];
            backtrack(nums, track, used);
            return res;
        }

        // 路径：记录在track中
        // 选择列表：nums中不存在于track的那些元素（used[i] 为false）
        // 结束条件：nums中的元素全都在track中出现
        void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
            // 触发结束条件
            if (track.size() == nums.length) {
                res.add(new LinkedList<>(track));
                return;
            }
            for (int i = 0; i < nums.length; i++) {
                // 排除不合法的选择
                if (used[i]) {
                    // nums[i] 已经在track中，跳过
                    continue;
                }
                // 做选择
                track.add(nums[i]);
                used[i] = true;
                // 进入下一层决策树
                backtrack(nums, track, used);
                // 取消选择
                track.removeLast();
                used[i] = false;
            }
        }

        // 这也是回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高
        // 写backtrack函数时，需要维护走过的[路径]和当前可以做的[选择列表]，当触发[结束条件]时，将[路径]记入结果集。
        // 其核心就是for循环里面的递归，在递归调用之前[做选择]，在递归调用之后[撤销选择]。
    }

    // n 位二进制数的所有可能
    // 函数的输入是一个正整数 n，请你返回所有长度为 n 的二进制数（0、1 组成），你可以按任意顺序返回答案。
    static class GenerateBinaryNumber {
        List<String> res = new ArrayList<>();
        //回溯路径
        StringBuilder track = new StringBuilder();

        // 生成所有长度为n的二进制数
        List<String> generateBinaryNumber(int n) {
            backtrack(n, 0);
            return res;
        }

        // 回溯算法核心框架
        void backtrack(int n, int i) {
            if (i == n) {
                // 当递归深度等于n时，说明找到一个长度为n的二进制数，结束递归
                // i从0增加到n，所以递归树的高度为n+1
                res.add(track.toString());
                return;
            }
            // 选择有两种， 0和1
            // 所以递归树是一棵二叉树
            for (int val : new int[]{0, 1}) {
                // 做选择
                track.append(val);
                backtrack(n, i + 1);
                // 撤销选择
                track.deleteCharAt(track.length() - 1);
            }
        }
    }

    // 37. 解数独 labuladong 消耗时间：325ms
    // 编写一个程序，通过填充空格来解决数独问题。
    // 数独的解法需 遵循如下规则：
    // 数字 1-9 在每一行只能出现一次。
    // 数字 1-9 在每一列只能出现一次。
    // 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
    // 数独部分空格内已填入了数字，空白格用 '.' 表示。
    // 输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
    // 输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
    // 提示：
    // board.length == 9
    // board[i].length == 9
    // board[i][j] 是一位数字或者 '.'
    // 题目数据 保证 输入数独仅有一个解
    static class SolveSudoku {
        // 标记是否已经找到可行解
        boolean found = false;

        // labuladong回溯算法
        public void solveSudoku(char[][] board) {
            backtrack(board, 0);
        }

        // 路径：board中小于index的位置所填的数字
        // 选择列表：数字1-9；
        // 结束条件：整个board都填满数字
        void backtrack(char[][] board, int index) {
            if (found) {
                // 已经找到一个可行解，立即结束
                return;
            }
            int m = 9;
            int n = 9;
            int i = index / n;
            int j = index % n;
            if (index == m * n) {
                // 找到一个可行解，触发base case
                found = true;
                return;
            }
            if (board[i][j] != '.') {
                // 如果有预设数字，不用我们穷举
                backtrack(board, index + 1);
                return;
            }
            for (char ch = '1'; ch <= '9'; ch++) {
                // 剪枝：如果遇到不合法的数字，就跳过
                if (!isValid(board, i, j, ch)) {
                    continue;
                }
                // 做选择
                board[i][j] = ch;
                backtrack(board, index + 1);
                if (found) {
                    // 如果找到一个可行解，立即结束
                    // 不要撤销选择，否则board[i][j]会被置为'.'
                    return;
                }
                // 撤销选择
                board[i][j] = '.';
            }
        }

        /**
         * 判断是否可以在(r, c)位置放置数字num
         *
         * @param board 棋盘
         * @param r     表示要检查位置的行索引
         * @param c     表示要检查位置的列索引
         * @param num   代表要尝试填入该位置的字符
         * @return 若在该位置填入num是合法的，返回true；反之，返回false。
         */
        boolean isValid(char[][] board, int r, int c, char num) {
            for (int i = 0; i < 9; i++) {
                // 判断行是否存在重复
                if (board[r][i] == num) {
                    return false;
                }
                // 判断列是否存在重复
                if (board[i][c] == num) {
                    return false;
                }
                // 判断 3 x 3 方框是否存在重复
                if (board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == num) {
                    return false;
                }
            }
            return true;
        }
    }

    // 37. 解数独 代码随想录 消耗时间：214ms
    static class SolveSudoku1 {
        public void solveSudoku(char[][] board) {
            solveSudokuHelper(board);
        }

        boolean solveSudokuHelper(char[][] board) {
            //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
            // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
            for (int i = 0; i < 9; i++) { // 遍历行
                for (int j = 0; j < 9; j++) { // 遍历列
                    if (board[i][j] != '.') { // 跳过原始数字
                        continue;
                    }
                    for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
                        if (isValidSudoku(i, j, k, board)) {
                            board[i][j] = k;
                            // 因为上述是被赋值了，所以不用裁剪
                            if (solveSudokuHelper(board)) { // 如果找到合适一组立刻返回
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    // 9个数都试完了，都不行，那么就返回false
                    return false;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适的棋盘位置了。
            return true;
        }

        /**
         * 判断棋盘是否合法有如下三个维度
         * 同行是否重复
         * 同列是否重复
         * 9宫格是否重复
         *
         * @param row   行
         * @param col   列
         * @param val   当前赋值
         * @param board 棋盘
         * @return
         */
        boolean isValidSudoku(int row, int col, char val, char[][] board) {
            // 同行是否重复
            for (int i = 0; i < 9; i++) {
                if (board[row][i] == val) {
                    return false;
                }
            }
            // 同列是否重复
            for (int j = 0; j < 9; j++) {
                if (board[j][col] == val) {
                    return false;
                }
            }
            // 9宫格里3X3小格内是否有重复
            // 确定九宫格的起始位置：
            // startRow = (row / 3) * 3：通过整数除法 row / 3 得到当前行所在的 3x3 九宫格的行编号（从 0 开始），
            // 再乘以 3 得到该九宫格的起始行索引。
            // startCol = (col / 3) * 3：同理，得到当前列所在的 3x3 九宫格的列编号，
            // 再乘以 3 得到该九宫格的起始列索引。
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++) {
                for (int j = startCol; j < startCol + 3; j++) {
                    if (board[i][j] == val) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

    // 51. N皇后问题
    // 输入：n = 4
    // 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
    // 解释：如上图所示，4 皇后问题存在两个不同的解法。
    // 不能同行
    // 不能同列
    // 不能同斜线

    /*
    回溯三部曲
    void backtracking(参数) {
        if (终止条件) {
            存放结果;
            return;
        }
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }
    - 递归函数参数
    - 递归终止条件
    - 单层搜索的逻辑
    */
    static class SolveNQueens {
        List<List<String>> res = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            char[][] chessboard = new char[n][n];
            for (char[] c : chessboard) {
                java.util.Arrays.fill(c, '.');
            }
            backtrack(n, 0, chessboard);
            return res;
        }

        public void backtrack(int n, int row, char[][] chessboard) {
            if (row == n) {
                res.add(arrayToList(chessboard));
                return;
            }
            for (int col = 0; col < n; ++col) {
                if (isValid(row, col, n, chessboard)) {
                    chessboard[row][col] = 'Q';
                    backtrack(n, row + 1, chessboard);
                    chessboard[row][col] = '.';
                }
            }
        }

        public boolean isValid(int row, int col, int n, char[][] chessboard) {
            // 检查列
            for (int i = 0; i < row; ++i) {
                if (chessboard[i][col] == 'Q') {
                    return false;
                }
            }
            // 检查45度对角线,左上角
            for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }
            // 检查135度对角线，右上角
            for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
                if (chessboard[i][j] == 'Q') {
                    return false;
                }
            }
            return true;
        }

        public List<String> arrayToList(char[][] chessboard) {
            List<String> list = new ArrayList<>();
            for (char[] c : chessboard) {
                list.add(String.copyValueOf(c));
            }
            return list;
        }
    }

    // 回溯算法秒杀所有排列/组合/子集问题
    /*
     * 无论是排列、组合还是子集问题，简单来说无非就是让你从序列nums中以给定规则取若干元素，主要有以下几种变体
     * 形式一：元素无重不可复选，即nums中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式；
     * 形式二：元素可重不可复选，即nums中的元素可以存在重复，每个元素最多只能被使用一次；
     * 形式三：元素无重可复选，即nums中的元素都是唯一的，每个元素可以被使用若干次。
     */

    // 1. 子集（元素无重不可复选）
    // 题目给你输入一个无重复元素的数组 nums，其中每个元素最多使用一次，请你返回 nums 的所有子集。
    // 换句话说，我们通过保证元素之间的相对顺序不变来防止出现重复的子集
    static class Subsets {
        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯算法的递归路径
        LinkedList<Integer> track = new LinkedList<>();

        // 主函数
        public List<List<Integer>> subsets(int[] nums) {
            backtrack(nums, 0);
            return res;
        }

        // 回溯算法的核心函数，遍历子集问题的回溯树
        void backtrack(int[] nums, int start) {
            // 前序位置，每个节点的值都是一个子集
            // 最后，backtrack 函数开头看似没有 base case，会不会进入无限递归？
            // 其实不会的，当 start == nums.length 时，叶子节点的值会被装入 res，但 for 循环不会执行，也就结束了递归。
            res.add(new LinkedList<>(track));
            // 回溯算法标准框架
            for (int i = start; i < nums.length; i++) {
                // 做选择
                track.addLast(nums[i]);
                backtrack(nums, i + 1);
                // 撤销选择
                track.removeLast();
            }
        }
    }

    // 2. 组合（元素无重不可复选）
    // 组合和子集是一样的：大小为 k 的组合就是大小为 k 的子集。
    // 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
    static class Combine {
        // 给你输入一个数组 nums = [1,2..,n] 和一个正整数 k，请你生成所有大小为 k 的子集。
        // 还是以 nums = [1,2,3] 为例，刚才让你求所有子集，就是把所有节点的值都收集起来；
        // 现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：

        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯算法的递归路径
        LinkedList<Integer> track = new LinkedList<>();

        // 主函数
        public List<List<Integer>> combine(int n, int k) {
            backtrack(1, n, k); // 因为是从1到n所以这里设置为1
            return res;
        }

        void backtrack(int start, int n, int k) {
            // base case
            if (k == track.size()) {
                // 遍历到了第 k 层，收集当前节点的值
                res.add(new LinkedList<>(track));
                return;
            }
            // 回溯算法标准框架
            for (int i = start; i <= n; i++) {
                // 选择
                track.addLast(i);
                // 通过start参数控制树枝的遍历，避免产生重复的子集
                backtrack(i + 1, n, k);
                // 撤销选择
                track.removeLast();
            }
        }
    }

    //3. 排列（元素无重不可复选）
    // 给定一个不含重复数字的数组 nums，返回其所有可能的全排列。
    static class Permute1 {
        // 刚才讲的组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，
        // 通过固定元素的相对位置保证不出现重复的子集。
        // 但排列问题本身就是让你穷举元素的位置，nums[i] 之后也可以出现 nums[i] 左边的元素，
        // 所以之前的那一套玩不转了，需要额外使用 used 数组来标记哪些元素还可以被选择。
        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯算法的递归路径
        LinkedList<Integer> track = new LinkedList<>();
        // track 中的元素会被标记为true
        boolean[] used;

        // 主函数，输入一组不重复的数字，返回它们的全排列
        List<List<Integer>> permute(int[] nums) {
            used = new boolean[nums.length];
            backtrack(nums);
            return res;
        }

        // 回溯算法核心函数
        void backtrack(int[] nums) {
            // base case到达叶子节点
            if (track.size() == nums.length) {
                // 收集叶子节点上的值
                res.add(new LinkedList<>(track));
                return;
            }

            // 回溯算法标准框架
            for (int i = 0; i < nums.length; i++) {
                if (used[i]) {
                    continue;
                }
                // 做选择
                used[i] = true;
                track.addLast(nums[i]);
                // 进入下一层回溯树
                backtrack(nums);
                // 取消选择
                track.removeLast();
                used[i] = false;
            }
        }

        // 但如果题目不让你算全排列，而是让你算元素个数为 k 的排列，怎么算？
        // 也很简单，改下 backtrack 函数的 base case，仅收集第 k 层的节点值即可：

        List<List<Integer>> permute1(int[] nums, int k) {
            used = new boolean[nums.length];
            backtrack(nums, k);
            return res;
        }

        // 回溯算法核心函数
        void backtrack(int[] nums, int k) {
            // base case，到达第k层，收集节点的值
            if (track.size() == k) {
                // 第k层节点的值就是大小为k的排列
                res.add(new LinkedList<>(track));
                return;
            }
            // 回溯算法核心框架
            for (int i = 0; i < nums.length; i++) {
                if (used[i]) {
                    continue;
                }
                // 做选择
                used[i] = true;
                track.addLast(nums[i]);
                // 进入下一层回溯树
                backtrack(nums, k);
                // 取消选择
                track.removeLast();
                used[i] = false;
            }
        }
    }

    // 4. 子集/组合（元素可重不可复选）
    // 力扣第 90 题「子集 II」就是这样一个问题，给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集。
    static class SubsetsWithDup {
        // 体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过：
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            // 先排序，让相同的元素靠在一起
            java.util.Arrays.sort(nums);
            backtrack(nums, 0);
            return res;
        }

        void backtrack(int[] nums, int start) {
            // 前序位置，每个节点的值都是一个子集
            res.add(new LinkedList<>(track));
            for (int i = start; i < nums.length; i++) {
                // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                track.addLast(nums[i]);
                backtrack(nums, i + 1);
                track.removeLast();
            }
        }
    }

    // 我们说了组合问题和子集问题是等价的，所以我们直接看一道组合的题目吧，这是力扣第 40 题「组合总和 II」：
    // 给你输入 candidates 和一个目标和 target，从 candidates 中找出中所有和为 target 的组合。
    // candidates 可能存在重复元素，且其中的每个数字最多只能使用一次。
    // 说这是一个组合问题，其实换个问法就变成子集问题了：请你计算 candidates 中所有和为 target 的子集。
    // 所以这题怎么做呢？
    // 对比子集问题的解法，只要额外用一个 trackSum 变量记录回溯路径上的元素和，然后将 base case 改一改即可解决这道题：
    static class CombinationSum2 {
        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯的路径
        LinkedList<Integer> track = new LinkedList<>();
        // 记录track中元素之和
        int trackSum = 0;

        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            if (candidates.length == 0) {
                return res;
            }
            // 先排序，让相同的元素排在一起
            Arrays.sort(candidates);
            backtrack(candidates, 0, target);
            return res;
        }

        // 回溯算法主函数
        void backtrack(int[] nums, int start, int target) {
            // base case达到目标和，找到符合条件的组合
            if (trackSum == target) {
                res.add(new LinkedList<>(track));
                return;
            }
            // base caser，超过目标和，直接结束
            if (trackSum > target) {
                return;
            }

            // 回溯算法标准框架
            for (int i = start; i < nums.length; i++) {
                // 剪枝逻辑，值相同的树枝，只遍历第一条
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 做选择
                track.add(nums[i]);
                trackSum += nums[i];
                // 递归遍历下一层回溯树
                backtrack(nums, i + 1, target);
                // 撤销选择
                track.removeLast();
                trackSum -= nums[i];
            }
        }
    }

    // 216. 组合总和 III
    static class CombinationSum3 {
        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯的路径
        LinkedList<Integer> track = new LinkedList<>();
        // 记录track中元素之和
        int trackSum = 0;

        public List<List<Integer>> combinationSum3(int k, int n) {
            int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
            backtrack(nums, 0, k, n);
            return res;
        }

        // 回溯算法主函数
        void backtrack(int[] nums, int start, int k, int target) {
            // base case达到目标和,并且k的长度等于track的长度，找到符合条件的组合
            if (trackSum == target && k == track.size()) {
                res.add(new LinkedList<>(track));
                return;
            }
            // base case，超过目标和，直接结束
            if (trackSum > target) {
                return;
            }

            // 回溯算法标准框架
            for (int i = start; i < nums.length; i++) {
                // 剪枝逻辑，值相同的树枝，只遍历第一条
                if (i > start && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 做选择
                track.add(nums[i]);
                trackSum += nums[i];
                // 递归遍历下一层回溯树
                backtrack(nums, i + 1, k, target);
                // 撤销选择
                track.removeLast();
                trackSum -= nums[i];
            }
        }
    }

    // 5. 排列（元素可重不可复选）
    // 力扣第 47 题「全排列 II」：给你输入一个可包含重复数字的序列 nums，请你写一个算法，返回所有可能的全排列
    static class PermuteUnique {
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> track = new LinkedList<>();
        boolean[] used;

        public List<List<Integer>> permuteUnique(int[] nums) {
            // 先排序，让相同的元素靠在一起
            java.util.Arrays.sort(nums);
            used = new boolean[nums.length];
            backtrack(nums);
            return res;
        }

        void backtrack(int[] nums) {
            if (track.size() == nums.length) {
                res.add(new LinkedList<>(track));
                return;
            }

            for (int i = 0; i < nums.length; i++) {
                if (used[i]) {
                    continue;
                }
                // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
                // 关于排列有重复元素问题，为什么要使用!used[i-1]，我的一个理解是这样做到了同层剪枝，而父子结构不能剪枝。
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                    continue;
                }
                track.add(nums[i]);
                used[i] = true;
                backtrack(nums);
                track.removeLast();
                used[i] = false;
            }
        }

        public static void main(String[] args) {
            int[] nums = new int[]{1, 2, 2};
            new PermuteUnique().permuteUnique(nums);
        }
    }

    // 6. 子集/组合（元素无重可复选）
    // 输入数组无重复元素，但每个元素可以被无限次使用。
    // 第 39 题「组合总和」：给你一个无重复元素的整数数组 candidates 和一个目标和 target，找出 candidates 中
    // 可以使数字和为目标数 target 的所有组合。candidates 中的每个数字可以无限制重复被选取。
    // 比如输入 candidates = [1,2,3], target = 3，算法应该返回：
    // [ [1,1,1],[1,2],[3] ]
    static class CombinationSum {
        // 这道题说是组合问题，实际上也是子集问题：candidates 的哪些子集的和为 target？

        List<List<Integer>> res = new LinkedList<>();
        // 记录回溯的路径
        LinkedList<Integer> track = new LinkedList<>();
        int trackSum = 0;

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            if (candidates.length == 0) {
                return res;
            }
            backtrack(candidates, 0, target);
            return res;
        }

        // 回溯算法主函数
        void backtrack(int[] nums, int start, int target) {
            // base case，找到目标和，记录结果
            if (trackSum == target) {
                res.add(new LinkedList<>(track));
                return;
            }
            // base case，超过目标和，停止向下遍历
            if (trackSum > target) {
                return;
            }
            // 回溯算法标准框架
            for (int i = start; i < nums.length; i++) {
                // 选择nums[i]
                trackSum += nums[i];
                track.add(nums[i]);
                // 递归遍历下一层回溯树(如果我想让每个元素被重复使用，我只要把 i + 1 改成 i 即可：)
                backtrack(nums, i, target);
                // 同一元素可重复使用，注意参数
                // 撤销选择nums[i]
                trackSum -= nums[i];
                track.removeLast();
            }
        }

        // 7. 排列（元素无重可复选）
        // 力扣上没有题目直接考察这个场景，我们不妨先想一下，nums 数组中的元素无重复且可复选的情况下，会有哪些排列？
        // 如输入 nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：
        // [
        //  [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
        //  [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
        //  [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
        //]
        // 标准的全排列算法利用 used 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 used 数组的剪枝逻辑就行了。
        static class PermuteRepeat {
            List<List<Integer>> res = new LinkedList<>();
            LinkedList<Integer> track = new LinkedList<>();

            public List<List<Integer>> permuteRepeat(int[] nums) {
                backtrack(nums);
                return res;
            }

            // 回溯算法核心函数
            void backtrack(int[] nums) {
                // base case,到达叶子节点
                if (track.size() == nums.length) {
                    res.add(new LinkedList<>(track));
                    return;
                }

                // 回溯算法标准框架
                for (int i = 0; i < nums.length; i++) {
                    // 做选择
                    track.add(nums[i]);
                    // 进入下一层回溯树
                    backtrack(nums);
                    // 取消选择
                    track.removeLast();
                }
            }
        }
    }

    // 一文秒杀所有岛屿题目
    // 岛屿系列题目的核心考点就是用 DFS/BFS 算法遍历二维数组。

    static class TwoDimensionalMatrix {
        // 二叉树的遍历
        void traverse(TreeNode root) {
            traverse(root.left);
            traverse(root.right);
        }

        // 二维矩阵遍历框架
        void dfs(int[][] grid, int i, int j, boolean[][] visited) {
            int m = grid.length;
            int n = grid[0].length;
            // 剪枝
            if (i < 0 || j > 0 || i >= m || j >= n) {
                // 超出索引边界
                return;
            }
            // 剪枝
            if (visited[i][j]) {
                // 已遍历过（i，j）
                return;
            }
            // 进入当前节点
            // 做选择
            visited[i][j] = true;
            // 进入相邻节点（四叉树）
            // 上
            dfs(grid, i - 1, j, visited);
            // 下
            dfs(grid, i + 1, j, visited);
            // 左
            dfs(grid, i, j - 1, visited);
            // 右
            dfs(grid, i, j + 1, visited);

            // 因为二维矩阵本质上是一幅「图」，所以遍历的过程中需要一个 visited 布尔数组防止走回头路，
            // 如果你能理解上面这段代码，那么搞定所有岛屿系列题目都很简单。
        }

        // 使用[方向数组]来处理上下左右的遍历
        // 方向数组，分别代表上下左右
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        void dfs1(int[][] grid, int i, int j, boolean[][] visited) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n) {
                // 超出索引边界
                return;
            }
            if (visited[i][j]) {
                // 已遍历过[i, j]
                return;
            }
            // 进入节点(i, j)
            visited[i][j] = true;
            // 递归遍历上下左右的节点
            for (int[] d : dirs) {
                int next_i = i + d[0];
                int next_j = j + d[1];
                dfs1(grid, next_i, next_j, visited);
            }
            // 离开节点(i, j)
            // 这种写法无非就是用for循环处理上下左右的遍历罢了
        }
    }

    // 岛屿数量
    // 这是力扣第 200 题「岛屿数量」，最简单也是最经典的一道问题，题目会输入一个二维数组 grid，
    // 其中只包含 0 或者 1，0 代表海水，1 代表陆地，且假设该矩阵四周都是被海水包围着的。
    static class NumIslands {
        // 主函数，计算岛屿数量
        public int numIslands(char[][] grid) {
            int res = 0;
            int m = grid.length;
            int n = grid[0].length;
            // 遍历grid
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1') {
                        // 每发现一个岛屿，岛屿数量加1
                        // 为什么每次遇到岛屿，都要用 DFS 算法把岛屿「淹了」呢？主要是为了省事，避免维护 visited 数组。
                        res++;
                        dfs(grid, i, j);
                    }
                }
            }
            return res;
        }

        // 从（i，j）开始，将与之相邻的陆地都变成海水
        void dfs(char[][] grid, int i, int j) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n) {
                // 超出索引边界
                return;
            }
            if (grid[i][j] == '0') {
                // 已经是海水了
                return;
            }
            // 将（i,j）变成海水
            grid[i][j] = '0';
            // 淹没上下左右的陆地
            dfs(grid, i + 1, j);
            dfs(grid, i, j + 1);
            dfs(grid, i - 1, j);
            dfs(grid, i, j - 1);
        }
    }

    // 封闭的岛屿
    // 力扣第 1254 题「统计封闭岛屿的数目」和上一题有两点不同：
    // 1、用 0 表示陆地，用 1 表示海水。
    // 2、让你计算「封闭岛屿」的数目。所谓「封闭岛屿」就是上下左右全部被 1 包围的 0，也就是说靠边的陆地不算作「封闭岛屿」。
    // 那么如何判断「封闭岛屿」呢？其实很简单，把上一题中那些靠边的岛屿排除掉，剩下的不就是「封闭岛屿」了吗？
    static class ClosedIsland {
        // 主函数：计算封闭岛屿的数量
        public int closedIsland(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            for (int j = 0; j < n; j++) {
                // 把靠上边的岛屿淹没
                dfs(grid, 0, j);
                // 把靠下边的岛屿淹没
                dfs(grid, m - 1, j);
            }

            for (int i = 0; i < m; i++) {
                // 把靠左边的岛屿淹没
                dfs(grid, i, 0);
                // 把靠右边的岛屿淹没
                dfs(grid, i, n - 1);
            }

            // 遍历grid，剩下的岛屿都是封闭岛屿
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 0) {
                        res++;
                        dfs(grid, i, j);
                    }
                }
            }
            return res;
        }

        // 从（i,j）开始，将与之相邻的陆地都变成海水
        void dfs(int[][] grid, int i, int j) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n) {
                return;
            }
            if (grid[i][j] == 1) {
                // 已经是海水了
                return;
            }
            // 将（i, j）变成水
            grid[i][j] = 1;
            // 淹没上下左右的陆地
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
            // 只要提前把靠边的陆地都淹掉，然后算出来的就是封闭岛屿了。
        }
    }

    // 岛屿的最大面积
    // 这是力扣第 695 题「岛屿的最大面积」，0 表示海水，1 表示陆地，现在不让你计算岛屿的个数了，而是让你计算最大的那个岛屿的面积，函数签名如下：
    static class MaxAreaOfIsland {
        // 这题的大体思路和之前完全一样，只不过 dfs 函数淹没岛屿的同时，还应该想办法记录这个岛屿的面积。
        public int maxAreaOfIsland(int[][] grid) {
            // 记录岛屿的最大面积
            int res = 0;
            int m = grid.length;
            int n = grid[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        // 淹没岛屿，并更新最大岛屿面积
                        res = Math.max(res, dfs(grid, i, j));
                    }
                }
            }
            return res;
        }

        // 有返回值的dfs
        // 淹没与（i, j）相邻的陆地，并返回淹没的陆地面积
        int dfs(int[][] grid, int i, int j) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n) {
                // 超出索引边界
                return 0;
            }
            if (grid[i][j] == 0) {
                // 已经是海水了
                return 0;
            }
            // 将（i，j）变成海水
            grid[i][j] = 0;
            return dfs(grid, i - 1, j) + dfs(grid, i + 1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1) + 1;
        }
    }

    // 子岛屿数量
    // 给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。
    // 一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
    // 如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，
    // 那么我们称 grid2 中的这个岛屿为 子岛屿 。
    // 请你返回 grid2 中 子岛屿 的 数目 。

    // 这道题的关键在于，如何快速判断子岛屿？肯定可以借助
    // Union Find 并查集算法 来判断，不过本文重点在 DFS 算法，就不展开并查集算法了。
    // 什么情况下 grid2 中的一个岛屿 B 是 grid1 中的一个岛屿 A 的子岛？
    // 当岛屿 B 中所有陆地在岛屿 A 中也是陆地的时候，岛屿 B 是岛屿 A 的子岛。
    // 反过来说，如果岛屿 B 中存在一片陆地，在岛屿 A 的对应位置是海水，那么岛屿 B 就不是岛屿 A 的子岛。
    // 那么，我们只要遍历 grid2 中的所有岛屿，把那些不可能是子岛的岛屿排除掉，剩下的就是子岛。
    static class CountSubIslands {
        public int countSubIslands(int[][] grid1, int[][] grid2) {
            int m = grid1.length;
            int n = grid1[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid1[i][j] == 0 && grid2[i][j] == 1) {
                        // 这个岛屿肯定不是子岛屿，淹掉
                        dfs(grid2, i, j);
                    }
                }
            }
            // 现在grid2中剩下的岛屿都是子岛屿，计算岛屿数量
            int res = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid2[i][j] == 1) {
                        res++;
                        dfs(grid2, i, j);
                    }
                }
            }
            return res;
        }

        // 从 (i, j) 开始，将与之相邻的陆地都变成海水
        void dfs(int[][] grid, int i, int j) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n) {
                return;
            }
            if (grid[i][j] == 0) {
                return;
            }
            grid[i][j] = 0;
            dfs(grid, i - 1, j);
            dfs(grid, i + 1, j);
            dfs(grid, i, j - 1);
            dfs(grid, i, j + 1);
        }
    }

    // 不同的岛屿数量
    // 力扣第 694 题「不同的岛屿数量」，题目还是输入一个二维矩阵，0 表示海水，1 表示陆地，这次让你计算 不同的 (distinct) 岛屿数量
    static class NumDistinctIslands {
        public int numDistinctIslands(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            // 记录所有岛屿的序列化结果
            HashSet<String> islands = new HashSet<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        // 淹掉这个岛屿，同时存储岛屿的序列化结果
                        StringBuilder sb = new StringBuilder();
                        dfs(grid, i, j, sb, 666);
                        islands.add(sb.toString());
                    }
                }
            }
            return islands.size();
        }

        /**
         * 首先，对于形状相同的岛屿，如果从同一起点出发，dfs 函数遍历的顺序肯定是一样的。
         * 这里类似回溯算法（关注点是树枝）
         * 假设它们的遍历顺序是：下，右，上，撤销上，撤销右，撤销下
         * 如果我用分别用 1, 2, 3, 4 代表上下左右，用 -1, -2, -3, -4 代表上下左右的撤销，那么可以这样表示它们的遍历顺序：
         * 你看，这就相当于是岛屿序列化的结果，只要每次使用 dfs 遍历岛屿的时候生成这串数字进行比较，就可以计算到底有多少个不同的岛屿了。
         * 细心的读者问到，为什么记录「撤销」操作才能唯一表示遍历顺序呢？不记录撤销操作好像也可以？不对，实际上必须记录撤销操作。
         * 比方说「下，右，撤销右，撤销下」和「下，撤销下，右，撤销右」显然是两个不同的遍历顺序，但如果不记录撤销操作，
         * 那么它俩都是「下，右」，成了相同的遍历顺序，显然是不对的。
         *
         * @param grid
         * @param i
         * @param j
         * @param sb
         * @param dir  记录方向
         */
        void dfs(int[][] grid, int i, int j, StringBuilder sb, int dir) {
            int m = grid.length;
            int n = grid[0].length;
            if (i < 0 || j < 0 || i >= m || j >= n || grid[i][j] == 0) {
                return;
            }
            // 前序遍历位置：进入（i,j）
            grid[i][j] = 0;
            sb.append(dir).append(',');
            // 上
            dfs(grid, i - 1, j, sb, 1);
            // 下
            dfs(grid, i + 1, j, sb, 2);
            // 左
            dfs(grid, i, j - 1, sb, 3);
            // 右
            dfs(grid, i, j + 1, sb, 4);

            // 后序遍历位置：离开（i, j）
            sb.append(-dir).append(',');
        }

        public static void main(String[] args) {
            int[][] grid = new int[][]{{1, 1, 0, 1, 1}, {1, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {1, 1, 0, 1, 1}};
            int nums = new NumDistinctIslands().numDistinctIslands(grid);
            System.out.println(nums);
        }
    }

    // 22. 括号生成
    // 括号问题可以简单分成两类，一类是括号的合法性判断，一类是合法括号的生成。
    // 对于括号合法性的判断，主要借助栈这种数据结构，而对于括号的生成，一般都要利用回溯算法进行暴力穷举
    static class GenerateParenthesis {
        // 有关括号问题，只要记住以下性质，思路就很容易想出来
        // 1. 一个合法括号组合的左括号数量一定等于右括号数量，这个很好理解
        // 2. 对于一个合法的括号字符串组合p，必然对于任何0<=i<len(p)都有：子串p[0..i]中左括号的数量都大于或等于右括号的数量
        // 如果不跟你说这个性质，可能不太容易发现，但是稍微想一下，
        // 其实很容易理解，因为从左往右算的话，肯定是左括号多嘛，到最后左右括号数量相等，说明这个括号组合是合法的。

        // 对于 2n 个位置，必然有 n 个左括号，n 个右括号，所以我们不是简单的记录穷举位置 i，
        // 而是用 left 记录还可以使用多少个左括号，用 right 记录还可以使用多少个右括号，这样就可以通过刚才总结的合法括号规律进行筛选了：

        // 回溯过程中的路径
        StringBuilder track = new StringBuilder();
        // 记录所有合法的括号组合
        List<String> res = new ArrayList<>();

        public List<String> generateParenthesis(int n) {
            if (n == 0) {
                return res;
            }
            // 可用的左括号和右括号数量初始化为n
            backtrack(n, n);
            return res;
        }

        // 可用的左括号数量为left个，可用的右括号数量为right个

        // 对于递归相关的算法，时间复杂度这样计算（递归次数）*（递归函数本身的时间复杂度）
        void backtrack(int left, int right) {
            // 若左括号剩下的多，说明不合法
            if (right < left) {
                return;
            }
            // 数量小于0肯定不合法
            if (left < 0 || right < 0) {
                return;
            }
            // 当所有括号都恰好用完时，得到一个合法的括号组合
            if (left == 0 && right == 0) {
                res.add(track.toString());
                return;
            }
            // 做选择，尝试放一个左括号
            track.append('(');
            backtrack(left - 1, right);
            // 撤销选择
            track.deleteCharAt(track.length() - 1);

            // 做选择，尝试放一个右括号
            track.append(')');
            backtrack(left, right - 1);
            // 撤销选择
            track.deleteCharAt(track.length() - 1);
        }
    }

    static class Demo {
        // for循环遍历nums数组
        public void demo1(int[] nums) {
            for (int index = 0; index < nums.length; index++) {
                System.out.println(nums[index]);
            }
        }
        // 只要调用 traverse(nums, 0)，和 for 循环的效果是完全一样的。

        // 递归遍历数组
        public void demo2(int[] nums) {
            traverse(nums, 0);
        }

        void traverse(int[] nums, int index) {
            if (index == nums.length) {
                return;
            }
            System.out.println(nums[index]);
            traverse(nums, index + 1);
        }
    }

    // 698. 划分为k个相等的子集
    // 给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
    // 示例 1：
    // 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
    // 输出： True
    // 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

    // 视角一，如果我们切换到这n个数字的视角，每个数字都要选择进入到k个桶里的某一个。
    // 视角二，如果我们切换到这k个桶里，对于每个桶，都要遍历nums中的n个数字，然后选择是否将当前遍历到的数字装进自己这个桶里。
    static class CanPartitionKSubsets {
        // 以数字的视角
        // 以数字的视角，选择 k 个桶，用 for 循环写出来是下面这样：
        /*
        // k 个桶（集合），记录每个桶装的数字之和
        int[] bucket = new int[k];

        // 穷举 nums 中的每个数字
        for (int index = 0; index < nums.length; index++) {
            // 穷举每个桶
            for (int i = 0; i < k; i++) {
                // nums[index] 选择是否要进入第 i 个桶
                // ...
            }
        }
        如果改成递归的形式，就是下面这段代码逻辑
        // k个桶（集合），记录每个桶装的数字之和
        int[] bucket = new int[k];

        // 穷举nums中的每个数字
        void backtrack(int[] nums, int index){
            // base case
            if(index == nums.length){
                return;
            }
            // 穷举每个桶
            for(int i = 0; i < bucket.length; i++){
                // 选择装进第i个桶里
                bucket[i] += nums[index];
                // 递归穷举下一个数字的选择
                backtrack(nums, index + 1);
                // 撤销选择
                bucket[i] -= nums[index];
            }
        }
        */
        public boolean canPartitionKSubsets(int[] nums, int k) {
            // 排除一些基本情况
            if (k > nums.length) {
                return false;
            }
            int sum = 0;
            for (int v : nums) {
                sum += v;
            }
            if (sum % k != 0) {
                return false;
            }

            // k个桶里（集合），记录每个桶装的数字之和
            int[] bucket = new int[k];
            // 理论上每个桶（集合）中数字的和
            int target = sum / k;
            // 穷举，看看nums是否能划分成k个和为target的子集
            return backtrack(nums, 0, bucket, target);
        }

        // 递归穷举nums中的每个数字
        boolean backtrack(int[] nums, int index, int[] bucket, int target) {
            if (index == nums.length) {
                // 检查所有桶的数字之和是否都是target
                for (int i = 0; i < bucket.length; i++) {
                    if (bucket[i] != target) {
                        return false;
                    }
                }
                // nums成功平分成k个子集
                return true;
            }

            // 穷举nums[index] 可能装入的桶
            for (int i = 0; i < bucket.length; i++) {
                // 剪枝，桶装满了
                if (bucket[i] + nums[index] > target) {
                    continue;
                }
                // 将nums[index] 装入bucket[i]
                bucket[i] += nums[index];
                // 递归穷举下一个数字的选择
                if (backtrack(nums, index + 1, bucket, target)) {
                    return true;
                }
                // 撤销选择
                bucket[i] -= nums[index];
            }
            // nums[index]装入哪个桶都不行
            return false;
        }
    }

    // 【练习】回溯算法经典习题 I

    // 967. 连续差相同的数字
    // 返回所有长度为 n 且满足其每两个连续位上的数字之间的差的绝对值为 k 的 非负整数 。
    // 请注意，除了 数字 0 本身之外，答案中的每个数字都 不能 有前导零。例如，01 有一个前导零，所以是无效的；但 0 是有效的。
    // 你可以按 任何顺序 返回答案。
    // 示例 1：
    // 输入：n = 3, k = 7
    // 输出：[181,292,707,818,929]
    // 解释：注意，070 不是一个有效的数字，因为它有前导零。

    // 基本思路：
    // 其实可以直接套框架秒掉对吧，其实就是考察前文 回溯算法描述排列组合的 9 种变体 中的「元素无重可复选的排列」。
    // 看出来了么？相当于给你 n 个盒子，然后你有 0~9 种球（元素）可以放进盒子，每个盒子只能放一个球，但每种球的数量无限，可以使用无数次。
    // 不过这道题比标准的「元素无重可复选的排列」多了两个剪枝逻辑：
    // 1、第一个数字不能是 0，因为题目要求数字不能以 0 开头；
    // 2、相邻两个数字的差的绝对值必须等于 k。
    static class NumsSameConsecDiff {
        List<Integer> res = new LinkedList<>();
        // 记录当前路径组成的数字的值
        int track = 0;
        // 记录当前数字的位数
        int digit = 0;

        public int[] numsSameConsecDiff(int n, int k) {
            backtrack(n, k);
            // Java需要把List<Integer>转成int[]
            int[] arr = new int[res.size()];
            for (int i = 0; i < res.size(); i++) {
                arr[i] = res.get(i);
            }
            return arr;
        }

        // 回溯算法核心函数
        void backtrack(int n, int k) {
            // base case，到达叶子节点
            if (digit == n) {
                // 找到一个合法的n位数
                res.add(track);
                return;
            }

            // 回溯算法标准框架
            for (int i = 0; i <= 9; i++) {
                // 本题的剪枝逻辑1，第一个数不能是0
                if (digit == 0 && i == 0){
                    continue;
                }
                // 本题的剪枝逻辑2，相邻两个数字的差的绝对值必须等于k
                // 重要，track % 10：表示求track最后一位
                if (digit > 0 && Math.abs(i - track % 10) != k){
                    continue;
                }
                // 做选择，在track尾部追加数字i
                digit++;
                track = 10 * track + i;
                // 进入下一层回溯树
                backtrack(n, k);
                track = track / 10; // 重要，撤销数字，比如52两位数，删除2，就需要用track = track / 10
                digit--;
            }
        }

        public static void main(String[] args) {
            new NumsSameConsecDiff().numsSameConsecDiff(3, 7);
        }
    }

}
